package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/clone-graph/
 */
public class Title133 {

    class Node {
        int val;

        List<Node> neighbors;

        Node(){
            val = 0;
            neighbors = new ArrayList<>();
        }

        Node(int val) {
            this.val = val;
            neighbors = new ArrayList<>();
        }

        Node(int val, List<Node> neighbors) {
            this.val = val;
            this.neighbors = neighbors;
        }
    }

    public Node cloneGraph(Node node) {
        //创建一个新的图<oldNode, newNode>
        Map<Node, Node> hash = new HashMap<>();
        return dfs(node,hash);
    }

    private Node dfs(Node node, Map<Node, Node> hash) {
        if (node == null) {
            return null;
        }
        //判断该节点是否被访问过,访问过则返回创建的新节点
        if (hash.containsKey(node)) {
            return hash.get(node);
        }
        //创建一个新的节点
        Node newNode = new Node(node.val, new ArrayList<>());
        //标记
        hash.put(node, newNode);
        for (Node node1 : node.neighbors) {
            newNode.neighbors.add(dfs(node1, hash));
        }
        return newNode;
    }

}
